﻿#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>

using namespace std;



////串联所有单词的子串
//vector<int> findSubstring1(string s, vector<string>& words) 
//{
//	unordered_map<string, int> hash1;
//	unordered_map<string, int> hash2;
//	int len = words[0].size();
//	vector<int> ret;
//	for (auto e : words)
//	{
//		hash1[e]++;
//	}
//	//滑动窗口划分len次 从0-len
//	for (int i = 0; i < len; i++)
//	{
//		for (int left = i, right = i; right < s.size(); right += len)
//		{
//
//			hash2.insert({ "s",1 });
//		}
//	}
//
//	return 0;
//}


//超出内存限制
//string TO_STRING(string s,int right,int len)
//{
//	string r;
//	while (len--)
//	{
//		string tmp;
//		tmp.push_back(s[right++]);
//		r += tmp;
//	}
//	return r;
//}
vector<int> findSubstring(string s, vector<string>& words)
{
	unordered_map<string, int> hash1;
	for (auto& e : words)
	{
		hash1[e]++;
	}
	int len = words[0].size();
	int m = words.size();
	vector<int> ret;
	for (int i = 0; i < len; i++)
	{
		unordered_map<string, int> hash2;
		for (int left = i, right = i,count=0; right +len <= s.size(); right += len)
		{

			string in = s.substr(right, len);
			hash2[in]++;
			if (hash1.count(in) && hash2[in] <= hash1[in])
			{
				count++;
			}
			if (right - left + 1 > len * m)
			{
				string out = s.substr(left, len);
				if (hash1.count(out) && hash2[out] <= hash1[out])
				{
					count--;
				}
				hash2[out]--;
				left += len;
			}
			if (count == m) ret.push_back(left);
		}
	}
    return ret;
}
int main()
{
	string s1("wordgoodgoodgoodbestword");
	vector<string> vs{ "word","good","best","good" };
	vector<int> ret = findSubstring(s1, vs);
	for (auto e : ret)
	{
		cout << e << " ";
	}

	return 0;
}